InforLorV4, Main, Exploration, bibRecord, 006A47

Quicksort with Unreliable Comparisons: A Probabilistic Analysis

Identifieur interne : 006A47 ( Main/Exploration ); précédent : 006A46; suivant : 006A48

Quicksort with Unreliable Comparisons: A Probabilistic Analysis

Auteurs : Laurent Alonso [France] ; Philippe Chassaing [France] ; Florent Gillet [France] ; Svante Janson [Suède, France] ; Edward M. Reingold [États-Unis, France] ; René Schott [France]

Source :

Combinatorics, Probability and Computing [ 0963-5483 ] ; 2004-07.

RBID : ISTEX:3337C3231676959FD0239DDAB76F693976F66263

Abstract

We provide a probabilistic analysis of the output of Quicksort when comparisons can err.

Url:

DOI: 10.1017/S0963548304006297

Affiliations:

Le document en format XML

<record><TEI wicri:istexFullTextTei="biblStruct"><teiHeader><fileDesc><titleStmt><title>Quicksort with Unreliable Comparisons: A Probabilistic Analysis</title>
<author><name sortKey="Alonso, Laurent" sort="Alonso, Laurent" uniqKey="Alonso L" first="Laurent" last="Alonso">Laurent Alonso</name>
</author>
<author><name sortKey="Chassaing, Philippe" sort="Chassaing, Philippe" uniqKey="Chassaing P" first="Philippe" last="Chassaing">Philippe Chassaing</name>
</author>
<author><name sortKey="Gillet, Florent" sort="Gillet, Florent" uniqKey="Gillet F" first="Florent" last="Gillet">Florent Gillet</name>
</author>
<author><name sortKey="Janson, Svante" sort="Janson, Svante" uniqKey="Janson S" first="Svante" last="Janson">Svante Janson</name>
</author>
<author><name sortKey="Reingold, Edward M" sort="Reingold, Edward M" uniqKey="Reingold E" first="Edward M." last="Reingold">Edward M. Reingold</name>
</author>
<author><name sortKey="Schott, Rene" sort="Schott, Rene" uniqKey="Schott R" first="René" last="Schott">René Schott</name>
</author>
</titleStmt>
<publicationStmt><idno type="wicri:source">ISTEX</idno>
<idno type="RBID">ISTEX:3337C3231676959FD0239DDAB76F693976F66263</idno>
<date when="2004" year="2004">2004</date>
<idno type="doi">10.1017/S0963548304006297</idno>
<idno type="url">https://api.istex.fr/ark:/67375/6GQ-G70QFHGD-F/fulltext.pdf</idno>
<idno type="wicri:Area/Istex/Corpus">000C05</idno>
<idno type="wicri:explorRef" wicri:stream="Istex" wicri:step="Corpus" wicri:corpus="ISTEX">000C05</idno>
<idno type="wicri:Area/Istex/Curation">000B98</idno>
<idno type="wicri:Area/Istex/Checkpoint">001655</idno>
<idno type="wicri:explorRef" wicri:stream="Istex" wicri:step="Checkpoint">001655</idno>
<idno type="wicri:doubleKey">0963-5483:2004:Alonso L:quicksort:with:unreliable</idno>
<idno type="wicri:Area/Main/Merge">006D51</idno>
<idno type="wicri:source">HAL</idno>
<idno type="RBID">Hal:hal-00005087</idno>
<idno type="url">https://hal.archives-ouvertes.fr/hal-00005087</idno>
<idno type="wicri:Area/Hal/Corpus">003E95</idno>
<idno type="wicri:Area/Hal/Curation">003E95</idno>
<idno type="wicri:Area/Hal/Checkpoint">004D28</idno>
<idno type="wicri:explorRef" wicri:stream="Hal" wicri:step="Checkpoint">004D28</idno>
<idno type="wicri:doubleKey">0963-5483:2004:Alonso L:quicksort:with:unreliable</idno>
<idno type="wicri:Area/Main/Merge">007278</idno>
<idno type="wicri:Area/Main/Curation">006A47</idno>
<idno type="wicri:Area/Main/Exploration">006A47</idno>
</publicationStmt>
<sourceDesc><biblStruct><analytic><title level="a">Quicksort with Unreliable Comparisons: A Probabilistic Analysis</title>
<author><name sortKey="Alonso, Laurent" sort="Alonso, Laurent" uniqKey="Alonso L" first="Laurent" last="Alonso">Laurent Alonso</name>
<affiliation wicri:level="3"><country wicri:rule="url">France</country>
<wicri:regionArea>INRIA-Lorraine and LORIA, Université Henri Poincaré-Nancy I, BP 239, 54506, Vandœuvre-lès-Nancy</wicri:regionArea>
<placeName><region type="region" nuts="2">Grand Est</region>
<region type="old region" nuts="2">Lorraine (région)</region>
<settlement type="city">Vandœuvre-lès-Nancy</settlement>
</placeName>
</affiliation>
<affiliation wicri:level="1"><country wicri:rule="url">France</country>
</affiliation>
</author>
<author><name sortKey="Chassaing, Philippe" sort="Chassaing, Philippe" uniqKey="Chassaing P" first="Philippe" last="Chassaing">Philippe Chassaing</name>
<affiliation></affiliation>
<affiliation wicri:level="1"><country wicri:rule="url">France</country>
</affiliation>
</author>
<author><name sortKey="Gillet, Florent" sort="Gillet, Florent" uniqKey="Gillet F" first="Florent" last="Gillet">Florent Gillet</name>
<affiliation wicri:level="3"><country wicri:rule="url">France</country>
<wicri:regionArea>Institut Élie Cartan, Université Henri Poincaré-Nancy I, BP 239, 54506, Vandœuvre-lès-Nancy</wicri:regionArea>
<placeName><region type="region" nuts="2">Grand Est</region>
<region type="old region" nuts="2">Lorraine (région)</region>
<settlement type="city">Vandœuvre-lès-Nancy</settlement>
</placeName>
</affiliation>
<affiliation wicri:level="1"><country wicri:rule="url">France</country>
</affiliation>
</author>
<author><name sortKey="Janson, Svante" sort="Janson, Svante" uniqKey="Janson S" first="Svante" last="Janson">Svante Janson</name>
<affiliation wicri:level="4"><orgName type="university">Université d'Uppsala</orgName>
<country>Suède</country>
<placeName><settlement type="city">Uppsala</settlement>
<region nuts="1">Svealand</region>
<region nuts="1">East Middle Sweden</region>
</placeName>
</affiliation>
<affiliation wicri:level="1"><country wicri:rule="url">France</country>
</affiliation>
</author>
<author><name sortKey="Reingold, Edward M" sort="Reingold, Edward M" uniqKey="Reingold E" first="Edward M." last="Reingold">Edward M. Reingold</name>
<affiliation wicri:level="2"><country xml:lang="fr">États-Unis</country>
<placeName><region type="state">Illinois</region>
</placeName>
<wicri:cityArea>Department of Computer Science, Illinois Institute of Technology, Stuart Building, 10 West 31st Street, Suite 236, Chicago</wicri:cityArea>
</affiliation>
<affiliation wicri:level="1"><country wicri:rule="url">France</country>
</affiliation>
</author>
<author><name sortKey="Schott, Rene" sort="Schott, Rene" uniqKey="Schott R" first="René" last="Schott">René Schott</name>
<affiliation wicri:level="3"><country wicri:rule="url">France</country>
<wicri:regionArea>Institut Élie Cartan and LORIA, Université Henri Poincaré-Nancy I, BP 239, 54506, Vandœuvre-lès-Nancy</wicri:regionArea>
<placeName><region type="region" nuts="2">Grand Est</region>
<region type="old region" nuts="2">Lorraine (région)</region>
<settlement type="city">Vandœuvre-lès-Nancy</settlement>
</placeName>
</affiliation>
<affiliation wicri:level="1"><country wicri:rule="url">France</country>
</affiliation>
</author>
</analytic>
<monogr></monogr>
<series><title level="j">Combinatorics, Probability and Computing</title>
<idno type="ISSN">0963-5483</idno>
<idno type="eISSN">1469-2163</idno>
<imprint><publisher>Cambridge University Press</publisher>
<pubPlace>Cambridge, UK</pubPlace>
<date type="published" when="2004-07">2004-07</date>
<biblScope unit="volume">13</biblScope>
<biblScope unit="issue">4-5</biblScope>
<biblScope unit="page" from="419">419</biblScope>
<biblScope unit="page" to="449">449</biblScope>
</imprint>
<idno type="ISSN">0963-5483</idno>
</series>
</biblStruct>
</sourceDesc>
<seriesStmt><idno type="ISSN">0963-5483</idno>
</seriesStmt>
</fileDesc>
<profileDesc><textClass></textClass>
<langUsage><language ident="en">en</language>
</langUsage>
</profileDesc>
</teiHeader>
<front><div type="abstract">We provide a probabilistic analysis of the output of Quicksort when comparisons can err.</div>
</front>
</TEI>
<affiliations><list><country><li>France</li>
<li>Suède</li>
<li>États-Unis</li>
</country>
<region><li>East Middle Sweden</li>
<li>Grand Est</li>
<li>Illinois</li>
<li>Lorraine (région)</li>
<li>Svealand</li>
</region>
<settlement><li>Uppsala</li>
<li>Vandœuvre-lès-Nancy</li>
</settlement>
<orgName><li>Université d'Uppsala</li>
</orgName>
</list>
<tree><country name="France"><region name="Grand Est"><name sortKey="Alonso, Laurent" sort="Alonso, Laurent" uniqKey="Alonso L" first="Laurent" last="Alonso">Laurent Alonso</name>
</region>
<name sortKey="Alonso, Laurent" sort="Alonso, Laurent" uniqKey="Alonso L" first="Laurent" last="Alonso">Laurent Alonso</name>
<name sortKey="Chassaing, Philippe" sort="Chassaing, Philippe" uniqKey="Chassaing P" first="Philippe" last="Chassaing">Philippe Chassaing</name>
<name sortKey="Gillet, Florent" sort="Gillet, Florent" uniqKey="Gillet F" first="Florent" last="Gillet">Florent Gillet</name>
<name sortKey="Gillet, Florent" sort="Gillet, Florent" uniqKey="Gillet F" first="Florent" last="Gillet">Florent Gillet</name>
<name sortKey="Janson, Svante" sort="Janson, Svante" uniqKey="Janson S" first="Svante" last="Janson">Svante Janson</name>
<name sortKey="Reingold, Edward M" sort="Reingold, Edward M" uniqKey="Reingold E" first="Edward M." last="Reingold">Edward M. Reingold</name>
<name sortKey="Schott, Rene" sort="Schott, Rene" uniqKey="Schott R" first="René" last="Schott">René Schott</name>
<name sortKey="Schott, Rene" sort="Schott, Rene" uniqKey="Schott R" first="René" last="Schott">René Schott</name>
</country>
<country name="Suède"><region name="Svealand"><name sortKey="Janson, Svante" sort="Janson, Svante" uniqKey="Janson S" first="Svante" last="Janson">Svante Janson</name>
</region>
</country>
<country name="États-Unis"><region name="Illinois"><name sortKey="Reingold, Edward M" sort="Reingold, Edward M" uniqKey="Reingold E" first="Edward M." last="Reingold">Edward M. Reingold</name>
</region>
</country>
</tree>
</affiliations>
</record>

Pour manipuler ce document sous Unix (Dilib)

EXPLOR_STEP=$WICRI_ROOT/Wicri/Lorraine/explor/InforLorV4/Data/Main/Exploration

HfdSelect -h $EXPLOR_STEP/biblio.hfd -nk 006A47 | SxmlIndent | more

HfdSelect -h $EXPLOR_AREA/Data/Main/Exploration/biblio.hfd -nk 006A47 | SxmlIndent | more

Pour mettre un lien sur cette page dans le réseau Wicri

{{Explor lien
   |wiki=    Wicri/Lorraine
   |area=    InforLorV4
   |flux=    Main
   |étape=   Exploration
   |type=    RBID
   |clé=     ISTEX:3337C3231676959FD0239DDAB76F693976F66263
   |texte=   Quicksort with Unreliable Comparisons: A Probabilistic Analysis
}}

This area was generated with Dilib version V0.6.33.
Data generation: Mon Jun 10 21:56:28 2019. Site generation: Fri Feb 25 15:29:27 2022

Serveur d'exploration sur la recherche en informatique en Lorraine

Quicksort with Unreliable Comparisons: A Probabilistic Analysis

Quicksort with Unreliable Comparisons: A Probabilistic Analysis

Source :

Abstract

Links toward previous steps (curation, corpus...)

Le document en format XML

Pour manipuler ce document sous Unix (Dilib)

Pour mettre un lien sur cette page dans le réseau Wicri

	Serveur d'exploration sur la recherche en informatique en Lorraine
	Attention, ce site est en cours de développement ! Attention, site généré par des moyens informatiques à partir de corpus bruts. Les informations ne sont donc pas validées.